/*************************************************************************
	> File Name: 005.hash_table.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/28 12:16:51 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//字符串进行哈希映射，冲突处理方法使用的是拉链法

/*
 * 结点的结构定义
 */
typedef struct Node {
    char *str;
    struct Node *next;
} Node;


typedef struct HashTable { //哈希表使用的是顺序表，每个位置上存储的是链表的首地址
    Node **data; //连续的存储空间存储结点的值
    int size;
} HashTable;

/*
 * 链表结点的初始化
 */
Node *init_node(char *str, Node *head) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->str = strdup(str); //strdup将传入的字符串拷贝一份，先动态申请一片空间，将传入的字符串存入，再返回拷贝后的字符串的首地址
    p->next = head;
    return p;
}

/*
 * 哈希表的初始化
 */
HashTable *init_hashTable(int n) {
    HashTable *h = (HashTable *)malloc(sizeof(HashTable));
    h->size = n << 1; //提升哈希表的效率，通常是将容量扩大一倍，实际上是存不了容量大小的个数函数的
    h->data = (Node **)calloc(h->size, sizeof(Node *)); //初始化的时候，哈希表的每个位置存储的是链表的首地址，都为空，于是使用calloc进行空间开辟
    return h;
}

/*
 * 对字符串进行哈希的哈希函数
 */
int BKDRHash(char *str) {
    int seed = 31, hash = 0;
    for (int i = 0; str[i]; i++) {
        hash = hash * seed + str[i];
    }
    return hash & 0x7fffffff;//保证结果为整数，因为hash可能为负数
}

/*
 * 哈希表的插入操作
 */
int insert(HashTable *h, char *str) { 
    int hash = BKDRHash(str);
    int ind = hash % h->size;
    h->data[ind] = init_node(str, h->data[ind]); //字符串封装为结点
    return 0;
}

/*
 * 哈希表的查找操作
 */
//根据哈希函数映射要查找的值的下标，查看该位置是否存储了目标值
int search(HashTable *h, char *str) {
    int hash = BKDRHash(str);
    int ind = hash % h->size;
    Node *p = h->data[ind]; //ind位置处为链表的首地址
    while (p && strcmp(p->str, str)) p = p->next;
    return p != NULL; //p不为空就找到了字符串
}

void clear_node(Node *node) {
    if (node == NULL) return ;
    Node *p = node;
    Node *q;
    while (p) {
        q = p->next;
        free(p->str); //因为p—>str是使用的strdup创建的，所以需要主动释放
        free(p);
        p = q;
    }
    return ;
}

void clear_hashTable(HashTable *h) {
    if (h == NULL) return ;
    for (int i = 0; i < h->size; i++) {
        clear_node(h->data[i]);
    }
    free(h->data);
    free(h);
    return ;
}

int main() {
    int op;
    #define max_n 100 
    char str[max_n + 5] = {0};
    HashTable *h = init_hashTable(max_n + 5);
    while (~scanf("%d%s", &op, str)) {
        switch (op) {
            case 0 :
                printf("insert %s to hash table\n", str);
                insert(h, str);
                break;
            case 1:
                printf("search %s from HashTable result = %d\n", str, search(h, str));
                break;
        }
    }
    #undef max_n 
    clear_hashTable(h);
    return 0;
}
